package com.leetcode.algorithm.y19.m04;

/**
 * leetcode-cn.com
 * (TODO)28. 实现strStr()
 * (done)209. 长度最小的子数组
 * @author: jie.deng
 * @time: 2019年4月12日 上午12:21:11
 */
public class MySolution0412 {
    
    /**
     * 28. 实现strStr() 
     * 实现 strStr() 函数。
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置
     * (从0开始)。如果不存在，则返回 -1。
     * 
     * 示例 1:
     * 输入: haystack = "hello", needle = "ll" 输出: 2 
     * 示例 2:
     * 输入: haystack = "aaaaa", needle = "bba" 输出: -1 
     * 说明:
     * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
     * 
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) { // needle是空字符串时返回 0
            return 0;
        }
        if (haystack.length() < needle.length()) {
            return -1;
        }
        int fromIdx = 0;
        int len = needle.length();
        while (fromIdx <= haystack.length() - len) {// 注意避免haystackChars[i + j]报数组越界异常
            boolean matched = true;
            for (int j = 0; j < len; j++) {
                if (needle.charAt(j) != haystack.charAt(fromIdx + j)) {
                    matched = false;
                    break;
                }
            }
            if (matched) {
                return fromIdx;
            }
            fromIdx++;  // 这里可以进一步优化
        }
        return -1;
    }
    
    /**
     * 209. 长度最小的子数组
     * 
     * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
     * 
     * 示例: 
     * 
     * 输入: s = 7, nums = [2,3,1,2,4,3]
     * 输出: 2
     * 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
     * 进阶:
     * 
     * 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
     * @param s
     * @param nums
     * @return
     */
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (s <= 0) {
            return 1;
        }
        int l = 0;
        int r = l;
        long sum = nums[0];
        while (sum < s && (r + 1) < nums.length) {
            sum += nums[++r];
        }
        if (sum < s) {
            return 0;
        }
        while (l < r && sum > s) {
            if (sum - nums[l] >= s) {
                sum -= nums[l++];
            } else {
                break;
            }
        }
        int min = r - l + 1;
        while (++r < nums.length) {
            sum += nums[r];
            sum -= nums[l++];
            while (l < r && sum > s) {
                if (sum - nums[l] >= s) {
                    sum -= nums[l++];
                    min--;
                } else {
                    break;
                }
            }
        }
        return min;
    }
    
}
